package com.learn.algorithm.exercises.nowcoder;

import java.util.LinkedList;

/**
 * @author wangxing
 * @version 2020/7/10 8:49 Administrator
 */
public class SpecialNum {
    /**
     * 链接：https://ac.nowcoder.com/acm/problem/202589
     * 来源：牛客网
     * <p>
     * 一天，牛妹找牛牛做一个游戏，牛妹给牛牛写了一个数字n，然后又给自己写了一个数字m，她希望牛牛能执行最少的操作将他的数字转化成自己的。
     * 操作共有三种，如下：
     * 1.在当前数字的基础上加一，如：4转化为5
     * 2.在当前数字的基础上减一，如：4转化为3
     * 3.将当前数字变成它的平方，如：4转化为16
     * 你能帮牛牛解决这个问题吗?
     * 输入：
     * 给定n,m,分别表示牛牛和牛妹的数字。
     * <p>
     * 输出：
     * 返回最少需要的操作数。
     * 输入
     * * 3,10
     * 输出
     * * 2
     *
     * @param n int整型 表示牛牛的数字
     * @param m int整型 表示牛妹的数字
     * @return int整型
     * 思路为每次对数字进行变动方式为3种,+1,-1,平方,得到的数字如果未曾出现,就放入到队列中,得到的数字如果出现了,就不做操作,直到最后得到所需数字
     */
    public static int getMinChangeNumber(int n, int m) {
        //使用bfs解题
        //设置可能出现数字的范围上限
        int maxSize = 2 * Math.max(m, n) + m;
        //按照数字范围定制数组,数组内存放得到当前数字所需的次数
        int[] arr = new int[maxSize];
        //制定一个队列,存放操作过程中生成的数字
        LinkedList<Integer> q = new LinkedList<>();
        //把初始数据n放入到双端队列中
        q.offer(n);
        while (!q.isEmpty()) {
            //获取第一个数字
            int t = q.pollFirst();
            //如果获取到与m相等则返回对应数组中的次数
            if (t == m) {
                return arr[t];
            }
            //获取temp值-1大于0的情况下,并且这个数字还未出现过,则进行-1操作,并将-1操作得到的temp放入到队列中,同时获取到temp-1所需的次数为temp获取的次数+1
            if (t - 1 > 0 && arr[t - 1] == 0) {
                arr[t - 1] = arr[t] + 1;
                q.offer(t - 1);
            }
            //获取temp值+1小于maxSize的情况下,并且这个数字还未出现过,则进行+1操作,并将+1操作得到的temp放入到队列中,同时获取到temp+1所需的次数为temp获取的次数+1
            if (t + 1 <= maxSize && arr[t + 1] == 0) {
                arr[t + 1] = arr[t] + 1;
                q.offer(t + 1);
            }
            //获取temp值*temp小于maxSize的情况下,并且这个数字还未出现过,则进行平方操作,并将平方操作得到的temp放入到队列中,同时获取到temp平方所需的次数为temp获取的次数+1
            if (t * t <= maxSize && arr[t * t] == 0) {
                arr[t * t] = arr[t] + 1;
                q.offer(t * t);
            }
        }
        return arr[m];
    }

}
